package 链表.删除链表的倒数的第n个节点;
/**
 * 题目描述
 * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
 * 输入：head = [1,2,3,4,5], n = 2
 * 输出：[1,2,3,5]
 * 力扣：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
 * 力扣第19题
 * */
/**
 * 删除链表的倒数第n个节点
 * 第一想法就是求出链表长度减去n+1的这个节点，就是要删除的节点
 * 首先遍历出链表的长度
 * 然后找到要删除的节点
 * 将节点删即可
 *
 * */

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 创建一个新的节点，新节点的值为0，指向原有列表节点的头部
        ListNode dumy = new ListNode(0,head);
        int length = getLength(head);
        ListNode cur = dumy;
        for(int i = 1;i < length -n + 1;i++){
            cur = cur.next;
        }
        // 删除节点
        cur.next = cur.next.next;
        // 获取链表头，因为使用了虚拟节点
        ListNode ans = dumy.next;
        return ans;
    }
    public int getLength(ListNode head){
        int length = 0;
        while(head != null){
            length++;
            head = head.next;
        }
        return length;
    }
}